using System.Collections.Generic;
using UnityEngine;

namespace IQIGame.Onigao.Framework
{
    public class QuadTree<T> where T : IQuadTreeObject
    {
        private const int MaxObjectsPerNode = 5;
        private const int MaxLevels = 5;

        private int _level;
        private QuadTree<T>[] _nodes;           //子节点 固定4个
        private Rect _bound;                    //格子范围
        private List<T> _storeObjects;          //格子内的物体

        public QuadTree(Rect bounds, int level = 0)
        {
            this._level = level;
            this._bound = bounds;
            this._storeObjects = new List<T>();
        }

        public void Insert(T objectToInsert)
        {
            //如果有了，就
            if (_nodes != null)
            {
                int nodeIndex = GetNodeToInsert(objectToInsert.quadTreePos);
                if (nodeIndex > -1)
                {
                    _nodes[nodeIndex].Insert(objectToInsert);
                }
                else
                {
                    //failed 
                }
                return;
            }

            _storeObjects.Add(objectToInsert);

            if (_storeObjects.Count > MaxObjectsPerNode && this._level < MaxLevels)
            {
                if (_nodes == null)
                {
                    float subWidth = _bound.width / 2;
                    float subHeight = _bound.height / 2;
                    float x = _bound.x;
                    float y = _bound.y;
                    _nodes = new QuadTree<T>[4];
                    int newLevel = _level + 1;
                    _nodes[0] = new QuadTree<T>(new Rect(x + subWidth, y, subWidth, subHeight), newLevel);
                    _nodes[1] = new QuadTree<T>(new Rect(x, y, subWidth, subHeight), newLevel);
                    _nodes[2] = new QuadTree<T>(new Rect(x, y + subHeight, subWidth, subHeight), newLevel);
                    _nodes[3] = new QuadTree<T>(new Rect(x + subWidth, y + subHeight, subWidth, subHeight), newLevel);
                }

                //Reallocate this quads objects into its children
                for (int i = 0; i < _storeObjects.Count; ++i)
                {
                    T storedObj = _storeObjects[i];
                    int iCell = GetNodeToInsert(storedObj.quadTreePos);
                    if (iCell > -1)
                    {
                        _nodes[iCell].Insert(storedObj);
                    }
                }

                //有子节点 本身不在存储
                _storeObjects.Clear();
            }
        }

        public void Remove(T objectToRemove)
        {
            if (ContainsLocation(objectToRemove.quadTreePos))
            {
                _storeObjects.Remove(objectToRemove);
                if (_nodes != null)
                {
                    for (int i = 0; i < 4; i++)
                    {
                        _nodes[i].Remove(objectToRemove);
                    }
                }
            }
        }

        public void Update(T objectToUpdate, Vector2 newPosition)
        {
            UpdateInternal(this, objectToUpdate, newPosition);
        }

        protected bool UpdateInternal(QuadTree<T> root, T objectToUpdate, Vector2 newPosition)
        {
            if (ContainsLocation(objectToUpdate.quadTreePos))
            {
                var index = _storeObjects.IndexOf(objectToUpdate);
                if (index >= 0)
                {
                    if (!ContainsLocation(newPosition))
                    {
                        //如果新的位置不在这个空间内,需要移除，然后重新插入
                        _storeObjects.RemoveAt(index);
                        objectToUpdate.quadTreePos = newPosition;
                        root.Insert(objectToUpdate);
                    }
                    else
                    {
                        objectToUpdate.quadTreePos = newPosition;
                    }
                    return true;
                }
                if (_nodes != null)
                {
                    for (int i = 0; i < 4; i++)
                    {
                        bool updated = _nodes[i].UpdateInternal(root, objectToUpdate, newPosition);
                        if (updated)
                        {
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        public void RetrieveObjects(List<T> returnObjects, Rect area)
        {
            if (!RectOverlap(area, _bound))
            {
                return;
            }
            for (int i = 0; i < _storeObjects.Count; i++)
            {
                if (area.Contains(_storeObjects[i].quadTreePos))
                {
                    returnObjects.Add(_storeObjects[i]);
                }
            }

            if (_nodes != null)
            {
                for (int i = 0; i < 4; i++)
                {
                    _nodes[i].RetrieveObjects(returnObjects, area);
                }
            }
        }

        public void Clear()
        {
            _storeObjects.Clear();

            for (int i = 0; i < _nodes.Length; i++)
            {
                var node = _nodes[i];
                if (node != null)
                {
                    node.Clear();
                    _nodes[i] = null;
                }
            }
        }

        public bool ContainsLocation(Vector2 location)
        {
            return _bound.Contains(location);
        }

        private int GetNodeToInsert(Vector2 location)
        {
            for (int i = 0; i < 4; i++)
            {
                if (_nodes[i].ContainsLocation(location))
                {
                    return i;
                }
            }
            return -1;
        }

        private bool ValueInRange(float value, float min, float max)
        {
            return (value >= min) && (value <= max);
        }

        /// <summary>
        /// 两个矩形是否重合
        /// </summary>
        /// <returns></returns>
        private bool RectOverlap(Rect A, Rect B)
        {
            bool xOverlap = ValueInRange(A.x, B.x, B.x + B.width) ||
                ValueInRange(B.x, A.x, A.x + A.width);

            bool yOverlap = ValueInRange(A.y, B.y, B.y + B.height) ||
                            ValueInRange(B.y, A.y, A.y + A.height);

            return xOverlap && yOverlap;
        }

        public void DrawDebug()
        {
            Gizmos.DrawLine(new Vector3(_bound.x, 0, _bound.y), new Vector3(_bound.x, 0, _bound.y + _bound.height));
            Gizmos.DrawLine(new Vector3(_bound.x, 0, _bound.y), new Vector3(_bound.x + _bound.width, 0, _bound.y));
            Gizmos.DrawLine(new Vector3(_bound.x + _bound.width, 0, _bound.y), new Vector3(_bound.x + _bound.width, 0, _bound.y + _bound.height));
            Gizmos.DrawLine(new Vector3(_bound.x, 0, _bound.y + _bound.height), new Vector3(_bound.x + _bound.width, 0, _bound.y + _bound.height));
            if (_nodes != null)
            {
                for (int i = 0; i < _nodes.Length; i++)
                {
                    if (_nodes[i] != null)
                    {
                        _nodes[i].DrawDebug();
                    }
                }
            }

            /*
            for (int i = 0; i < _storeObjects.Count; i++)
            {
                Gizmos.DrawSphere(V2toV3(_storeObjects[i].GetPosition()), m_minWidth * 0.02f);
            }
            */
        }

    }
}
